package leetcode.L994;

import java.util.ArrayDeque;
import java.util.Deque;


class Solution {

    public int orangesRotting(int[][] grid) {
        //记录腐烂橘子的位置
        Deque<int[]> deque = new ArrayDeque<>();
        //记录新鲜橘子数量，最后用以判断新鲜橘子是否>0来返回结果
        int freshNum = 0;
        int minute = 0;
        int rowLen = grid.length;
        int columnLen = grid[0].length;
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < columnLen; j++) {
                if (grid[i][j]==2) {
                    deque.offer(new int[]{i,j});
                } else if (grid[i][j]==1) {
                    freshNum++;
                }
            }
        }

        while (!deque.isEmpty()) {
            int size = deque.size();
            if (freshNum == 0) {
                return minute;
            }
            for (int i = 0; i < size; i++) {
                int[] rot = deque.poll();
                int x = rot[0];
                int y = rot[1];
                freshNum -= roting(grid, x - 1, y, deque);
                freshNum -= roting(grid, x + 1, y, deque);
                freshNum -= roting(grid, x, y - 1, deque);
                freshNum -= roting(grid, x, y + 1, deque);
            }
            minute++;
        }
        return freshNum > 0 ? -1 : minute;
    }

    public int roting(int[][] grid, int x, int y,Deque<int[]> queue) {
        if (x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1 || grid[x][y] != 1) {
            return 0;
        }
        // grid[x][y] = 1
        grid[x][y] = 2;
        queue.offer(new int[]{x, y});
        return 1;
    }
}